#include <cassert>
#include "SortTestHelper.h"
#include "InsertSort.h"
#include "SelectionSort.h"
#include "QuickSort.h"
#include "MergeSort.h"
#include "HeapSort.h"

template<typename T>
void TestSort(int arr[], int n)
{
	int* data = SortTestHelper::CopyArray(arr, n);
	T s;
	time_t begin = clock();
	s.Sort(data, n);
	time_t end = clock();
	assert(SortTestHelper::IsSorted(data, n));
	cout << typeid(T).name() << " use time " << double(end - begin) / CLOCKS_PER_SEC << endl;
	delete[] data;
}

int main()
{
	int num = 100000;

	cout << "\n random array sort" << endl;
	int* arr = SortTestHelper::GenerateRandomArray(num, 0, 50000);
	TestSort<SelectionSort<int>>(arr, num);
	TestSort<InsertSort<int>>(arr, num);
	TestSort<QuickSort1Way<int>>(arr, num);
	TestSort<QuickSort2Way<int>>(arr, num);
	TestSort<QuickSort3Way<int>>(arr, num);
	TestSort<MergeSort<int>>(arr, num);
	TestSort<MergeSortBU<int>>(arr, num);
	TestSort<HeapSort<int>>(arr, num);
	TestSort<HeapifySort<int>>(arr, num);
	delete[] arr;

	cout << "\n near sorted array sort" << endl;
	int* arr1 = SortTestHelper::GenerateNearSortedArray(num, 50);
	TestSort<SelectionSort<int>>(arr1, num);
	TestSort<InsertSort<int>>(arr1, num);
	TestSort<QuickSort1Way<int>>(arr1, num);
	TestSort<QuickSort2Way<int>>(arr1, num);
	TestSort<QuickSort3Way<int>>(arr1, num);
	TestSort<MergeSort<int>>(arr1, num);
	TestSort<MergeSortBU<int>>(arr1, num);
	TestSort<HeapSort<int>>(arr1, num);
	TestSort<HeapifySort<int>>(arr1, num);
	delete[] arr1;

	cout << "\n many repeat element array sort" << endl;
	int* arr2 = SortTestHelper::GenerateRandomArray(num, 0, 20);
	TestSort<SelectionSort<int>>(arr2, num);
	TestSort<InsertSort<int>>(arr2, num);
	TestSort<QuickSort1Way<int>>(arr2, num);
	TestSort<QuickSort2Way<int>>(arr2, num);
	TestSort<QuickSort3Way<int>>(arr2, num);
	TestSort<MergeSort<int>>(arr2, num);
	TestSort<MergeSortBU<int>>(arr2, num);
	TestSort<HeapSort<int>>(arr2, num);
	TestSort<HeapifySort<int>>(arr2, num);
	delete[] arr2;
	

	return 0;
}